#include <stdio.h>
#include <stdlib.h>
#include "heap.h"

FILE * LeArquivo(char *nomearq)
{
	FILE *arquivo;

	arquivo = fopen(nomearq,"r");

	return arquivo;
}

/* a partir da lista ordenada por frequencias monta uma lista ordenada pela tabela ascii */
void OrdenaAsc(ListaSimples **lista, ListaSimples **nova)
{
	ListaSimples *novoNo, *aux, *aux2;
	
	if(*lista == NULL) return; /* lista vazia */
	
	else
	{
		aux = *lista;
		*nova = (ListaSimples*)malloc(sizeof(ListaSimples));
		(*nova)->carac = aux->carac;
		(*nova)->freq = aux->freq;
		(*nova)->no = aux->no;
		(*nova)->prox = NULL;
		
		if(aux->prox != NULL)
			aux = aux->prox;
		else return; /* somente um elemento, a lista jah esta montada */
		
			
		while(aux != NULL)
		{
			novoNo = (ListaSimples*)malloc(sizeof(ListaSimples));
			novoNo->carac = aux->carac;
			novoNo->freq = aux->freq;
			novoNo->no = aux->no;
			
			if(aux->carac < (*nova)->carac) /* inserir no comeco */
			{
				novoNo->prox = *nova;
				*nova = novoNo;
			}
			
			else /* procura posicao correta para inserir */
			{
				aux2 = *nova;
				
				/* a posicao correta eh apos aux2 */
				while(aux2->prox != NULL && aux2->prox->carac < aux->carac)
					aux2 = aux2->prox;
				
				if(aux2->prox == NULL) /* inserir no final */
				{
					aux2->prox = novoNo;
					novoNo->prox = NULL;
				}
				
				else /* inserir entre dois elementos */
				{
					novoNo->prox = aux2->prox;
					aux2->prox = novoNo;
				}
			}
			
			aux = aux->prox;
		}
	}
}

void imprime_tabela_arquivo(char *nomearq)
{
	Heap *aux;
	ListaSimples *lista, *listaAsc, *auxList;
	Arvore *no;
	Lista *listaaux = NULL;
	FILE *entrada;

	entrada = LeArquivo(nomearq);

	aux = (Heap *)ContaeOrdena(entrada);
	lista = (ListaSimples *)MontaLista(aux);

	OrdenaAsc(&lista, &listaAsc);
	
	no = MontaArvore(&lista);

	/* imprime o numero de linhas */
	printf("%d\n",aux->tam);
	
	auxList = listaAsc;
	
	while(auxList != NULL)
	{
		printf("%d ", auxList->carac);
		AchaCaminho(auxList->no, &listaaux);
		auxList = auxList->prox;
	}
	
	LiberaListaSimples(&listaAsc);
	LiberaHeap(aux);

}

void descomprime_arquivo(char *nomearq)
{
	FILE *entrada;
	Arvore *arv;

	entrada = LeArquivo(nomearq);

	arv = (Arvore *)ReconstroiArv(entrada);

	SegueCaminho(entrada,arv);

	fclose(entrada);

	LiberaArvore(arv);
}

/* conta a frequencia total de caracteres do arquivo de entrada, isto eh, a soma de todas as frequencias */
int ContaFreq(ListaSimples *lista)
{
	ListaSimples *aux;
	int total = 0;
	
	if (lista == NULL) return; /* lista vazia */
		
	else
	{
		while(lista != NULL)
		{
			aux = lista;
			total += aux->freq;
			lista = lista->prox;
		}
	}
	
	return total;
}

/* monta lista na sequencia original do arquivo de entrada */
void MontaListaOri (char a, ListaSimples **lista)
{
	ListaSimples *novo, *aux;
	
	novo = (ListaSimples*)malloc(sizeof(ListaSimples));
	novo->carac = a;
	novo->prox = NULL;
	
	/* deve-se inserir sempre no final para ficar na ordem original da entrada */
	if( *lista == NULL) /* lista vazia */
		*lista = novo;
	
	else /* lista nao vazia, insere no final */
	{
		aux = *lista;
		
		while(aux->prox != NULL)
			aux = aux->prox; /* aux aponta para o ultimo elemento da lista */
			
		aux->prox = novo;
	}
}

/* busca o no correspondente do caracetere da lista da sequencia original */
Arvore* buscaCarac(char a, ListaSimples **lista)
{
	ListaSimples *temp;
	
	temp = *lista;
	
	if(temp == NULL) return;
	
	else
	{
		while(temp != NULL)
		{
			if(temp->carac == a)
				return temp->no;
			
			temp = temp->prox;
		}
	}
}

void codifica_arquivo (char *nomearq)
{
	FILE *entrada, *leituraAux;
	ListaSimples *lista, *listaOri, *listaTemp;
	Heap *aux;
	Lista *listaaux = NULL;
	Arvore *no, *res;
	int tamanho;
	char a;
	
	entrada = LeArquivo(nomearq);
	leituraAux = LeArquivo(nomearq);
	
	aux = (Heap *)ContaeOrdena(entrada);
	lista = (ListaSimples *)MontaLista(aux);
	
	tamanho = ContaFreq(lista);
	printf("%d\n", tamanho);
	printf("T\n");
	
	no = MontaArvore(&lista);
	
	listaOri = NULL;
	
	/* monta lista com a sequencia original da entrada */
	while(!feof(leituraAux))
	{
		fscanf(leituraAux, "%c", &a);
		if(!feof(leituraAux))
			MontaListaOri(a, &listaOri);
	}
	
	fclose(leituraAux);
	
	listaTemp = listaOri;
	
	
	/* sobre a lista tinham 2 opcoes, ou fazer uma copia ou nao liberar a memoria em MontaArvore. Achei melhor nao fazer a copia
	e liberar a memoria no final */
	
	while(listaTemp != NULL)
	{
		res = buscaCarac(listaTemp->carac, &lista);
		AchaCaminho(res, &listaaux);
		listaTemp = listaTemp->prox;
	}
	
	LiberaListaSimples(&listaOri);
	LiberaHeap(aux);
	
}
